home *** CD-ROM | disk | FTP | other *** search
/ CU Amiga Super CD-ROM 19 / CU Amiga Magazine's Super CD-ROM 19 (1998)(EMAP Images)(GB)[!][issue 1998-02].iso / CUCD / Programming / LEDA / README-3.1b < prev    next >
Text File  |  1994-08-05  |  12KB  |  404 lines
  1.  
  2. --------------------------------------------------------------------------------
  3.                LEDA-3.1b   (LEDA 3.1 Beta Test Release)
  4. --------------------------------------------------------------------------------
  5.  
  6. This is a pre-release of Version 3.1 to be released this summer.
  7. You can use it at your own risk. This file describes some of
  8. the changes and new features (not complete!). Some of this stuff
  9. may still be changed. Please report any problems, bugs, remarks, 
  10. and suggestions to leda@mpi-sb.mpg.de or leda-bugs@mpi-sb.mpg.de
  11.  
  12. Many changes were made to make LEDA work with new compilers (g++-2.5.8,
  13. lucid-c++, borland-4.0, ...) and with more machines/systems (silicon graphics,
  14. linux, ...). Below you find a list of the most important bugs that have been 
  15. fixed since release 3.0. There are also some new data types and algorithms 
  16. (especially in the graph and window section) described at the end of 
  17. this file. Note that the user manual is not up to date at the moment.
  18.  
  19.  
  20. Remark:
  21. We have received many problems reports on difficulties with g++
  22. and with parameterized data types if the actual type arguments are
  23. of a (user-defined) class type. Note that g++ (also the latest version)
  24. often cannot handle function templates correctly. As a work-around for
  25. this bug LEDA uses the "LEDA_TYPE_PARAMETER" macro as describen in
  26. the "Changes" file and in example programs "prog/basic/pair.c",
  27. "prog/basic/param.c". 
  28.  
  29.  
  30. Bugs (in version 3.0) fixed:
  31. --------------------------------------------------------------------------------
  32. - skiplist copy constructor
  33. - memory leaks in leda panels
  34. - nested forall-loops
  35. - string::read now can read strings of arbitrary length
  36. - made dlist::bucket_sort stable 
  37. - memory bug in dp_hash (dynamic perfect hashing) fixed
  38. - k_heap::del_item fixed
  39. - made rs_tree::change_inf (dictionary) clear old and copy new information
  40. - dlist::search (replaced != by call of virtual cmp function)
  41. - fixed bug in queue::append (replaced Convert by Copy)
  42. - bugs in MAX_WEIGHT_BIPARTITE_MATCHING fixed (by M. Paul)
  43. - prio.h: added missing ostream argument cout to Print calls
  44. - stack::push(x)    replaced Convert(x) by Copy(x)
  45. - segment::angle()  now returns zero for segments of length zero
  46. - memory leak in draw_(filled_)polygon fixed
  47. - bug in ab_tree::clear() fixed (forgot to set counter to zero)
  48. - made dlist update operations protected
  49. - missing operation ugraph::read(istream&) inserted
  50.  
  51.  
  52.  
  53. NEW FEATURES
  54.  
  55. --------------------------------------------------------------------------------
  56. Basics
  57. --------------------------------------------------------------------------------
  58.  
  59. - nested forall loops 
  60.  
  61. - singly linked lists   slist<T>   (<LEDA/slist.h>)
  62.  
  63. - compare and ord function arguments (used in list::sort, array::sort, 
  64.   list::bucket_sort, ...) have to use const reference parameters, i.e.,
  65.   have to be of type
  66.  
  67.   int cmp(const T&, const T&) 
  68.  
  69.   int ord(const T&)
  70.  
  71.  
  72.  
  73.  
  74. --------------------------------------------------------------------------------
  75. Graphs
  76. --------------------------------------------------------------------------------
  77.  
  78. Adjacency lists are now realized by deriving edges from a base list-element 
  79. class (obj_link). 
  80.  
  81.  
  82. Definition:
  83.  
  84. ... with each node is associated the list of incoming edges (in-edges)
  85. and the list of outgoing edges (out-edges) ...
  86.  
  87.  
  88. edge G.new_edge(v,w)
  89.        appends new edge(v,w) to the list of out-edges of v and to the list of
  90.        in-edges of w
  91.  
  92. edge G.new_edge(e1,w,d1)
  93.        inserts new edge(source(e1),w) before/after (if d1=before/after) edge e1
  94.        into out-list of source(e1) and appends it to the in-list of w
  95.  
  96. edge G.new_edge(e1,e2,d1,d2)
  97.        inserts new edge(source(e1),target(e2)) before/after (if d1=before/after)
  98.        edge e1 into the out-list of source(e1) and before/after (if d2=...)
  99.        edge e2 into the in-list of target(e2)
  100.  
  101. node G.opposite(v,e) 
  102.  
  103.  
  104. edge G.first_adj_edge();
  105. edge G.first_in_edge();
  106. edge G.last_adj_edge();
  107. edge G.last_in_edge();
  108. edge G.adj_succ(e);
  109. edge G.in_succ(e);
  110. edge G.cyclic_adj_succ(e);
  111. edge G.cyclic_in_succ(e);
  112. edge G.adj_pred(e);
  113. edge G.in_pred(e);
  114. edge G.cyclic_adj_pred(e);
  115. edge G.cyclic_in_pred(e);
  116.  
  117.  
  118. Iterations:
  119. -----------
  120.  
  121. forall_out_edges(e,v)   iterates over all out-edges of v
  122. forall_in_edges(e,v)    iterates over all in-edges of v
  123. forall_inout_edges(e,v) iterates over both out-edges and in-edges
  124.  
  125. forall_adj_edges(e,v) == forall_out_edges(e,v)
  126.  
  127.  
  128. Example applications of forall_in/out_edges macros :
  129. MAX_FLOW  (graph_alg/_maxflow.c)
  130. MIN_COST_MAX_FLOW  (graph_alg/_mcmflow.c)
  131.  
  132.  
  133. Undirected graphs (ugraph)
  134. -------------------------
  135. forall_adj_edges(e,v)  == forall_inout_edges(e,v) 
  136. (this is the only difference between directed and undirected graphs)
  137.  
  138. Here is still a problem: since forall_inout_edges is realized by a nested
  139. for-loop, the "break" command does not work as expected. You have to use
  140. the predefined LEDA macro "ADJ_BREAK" instead.
  141.  
  142.  
  143. other operations:
  144.  
  145.  
  146. void G.hide_edge(edge e)         removes an edge (temporarily) from its 
  147.                                  adjacency list, however, not from E
  148.                                  (list of all edges)
  149.                                 
  150. void G.restore_edge(edge e)      puts e back into its adjacency list
  151.  
  152.  
  153.  
  154. node_data<T>
  155. ------------
  156.  
  157. A faster and dynamic version of "node_array",
  158. occupies an additional pointer in the node data structure
  159.  
  160. RESTRICTIONS:
  161. - T has to be a pointer type or int
  162. - only one instance possible for every graph
  163.  
  164. header file:  <LEDA/graph.h>
  165.  
  166. example:  LEDA/prog/graph/shorttest.c
  167.  
  168.  
  169.  
  170. node_list
  171. ---------
  172.  
  173. Faster version of "list<node>"
  174.  
  175. RESTRICTIONS:
  176. - every node can be in at most one node_list
  177. - restricted set of operations:
  178.  
  179.   void L.append(node v)
  180.   void L.push(node v) 
  181.   void L.insert(node v, node w)
  182.   node L.pop()      
  183.   void L.del(node v)
  184.   bool L.member(node v)  (L(v) = L.member(v))
  185.   node L.first()
  186.   node L.last()
  187.   node L.succ(node v)
  188.   node L.pred(node v) 
  189.   node L.cyclic_succ(node v) 
  190.   node L.cyclic_pred(node v) 
  191.   forall(v,L)
  192.  
  193. header file:  <LEDA/graph.h>
  194.  
  195. example:  LEDA/prog/graph/shorttest.c
  196.  
  197.  
  198.  
  199. b_node_pq<int n>
  200. ----------------
  201.  
  202. bounded integer priority queue:  maximal difference of priorities <= n, 
  203. the minimum priority is non-decreasing, each node can be in at most one queue
  204.  
  205. Declaration: 
  206.    a) b_node_pq<n>  PQ;          // if PQ empty PQ.del_min() returns nil
  207.    b) b_node_pq<n>  PQ(node v);  // if PQ empty PQ.del_min() returns v 
  208.  
  209. Operations:
  210.    node PQ.del_min()
  211.    void PQ.insert(node,int) 
  212.    void PQ.del(node)
  213.  
  214.  
  215. Implementation: cyclic array of buckets (node_list)
  216.  
  217. header file:  <LEDA/b_node_pq.h>
  218.  
  219. example:  LEDA/prog/graph/shorttest.c
  220.  
  221.  
  222.  
  223. --------------------------------------------------------------------------------
  224. Algorithms:
  225. --------------------------------------------------------------------------------
  226.  
  227. The Efficiency of many Graphlgorithms has been improved,
  228. in particular: MAX_FLOW, MAX_WEIGHT_BIPARTITE_MATCHING, ...
  229.  
  230.  
  231. void random_planar_graph(graph& G,int n)    
  232.                                  generates a random planar graph G with n nodes
  233.  
  234. void random_planar_graph(graph& G, node_array<double>& xcoord, 
  235.                                    node_array<double>& ycoord, 
  236.                                    int n)
  237.                                  generates an embedded planar graph G with n 
  238.                                  nodes and double coordinates xcoord[v] and
  239.                                  ycoord[v] in [0..1] for each node v.
  240.                                
  241.  
  242. bool PLANAR(G)                   planarity test (should work now)
  243.  
  244. bool PLANAR(G,list<edge> E)      returns a Kuratowski-subgraph E, if
  245.                                  G is not planar (slow!)
  246.  
  247.  
  248. int MIN_COST_MAX_FLOW(const graph& G,node s,node t,const edge_array<int>& cap,
  249.                                                    const edge_array<int>& cost,
  250.                                                    edge_array<int>& flow);
  251.  
  252.                                  cmoputes  maximal flow  with minimal cost
  253.  
  254.  
  255.  
  256. --------------------------------------------------------------------------------
  257. window/graphics
  258. --------------------------------------------------------------------------------
  259.  
  260. - pure X implementation of the window stuff, i.e., you do not
  261.   have to link with openlook/xview libraries (-lolgx -lxview)
  262.   any more. The window library is called "libWx.a".
  263.  
  264.   CC  ... -lP -lG -lL -lWx -lX11 -lm
  265.  
  266.  
  267. - more than one window 
  268.   (see prog/graphics/windows.c)
  269.  
  270. - positioning of windows: window w(l,w,x,y)
  271.   where x and y is an integer or one of the following values:
  272.   window::min :   at left/upper screen boundary
  273.   window::max :   at right/lower screen boundary
  274.   winodw::center: center in corresponding dimension
  275.   (see prog/graphics/windows.c)
  276.  
  277. - default window label
  278.   can be specified in constructor
  279.   window w(l,w,x,y,label="")
  280.   window w(l,w,label="")
  281.   window w(label="")
  282.   (see prog/graphics/windows.c)
  283.  
  284. - colors
  285.   16 predefined colors:
  286.   white, black, blue, red, green, yellow, violet, orange,
  287.   cyan, brown, pink, green2, blue2, grey1, grey2, grey3
  288.   colors can be specified by name, i.e., a string from /usr/lib/X11/rgb.txt
  289.   (see prog/graphics/blue.c)
  290.  
  291.  
  292. - positioning of panels (does not work sith all window managers)
  293.  
  294.  P.open();             // center on screen
  295.  P.open(x,y);          // screen position (x,y)
  296.  P.open(W);            // center on window W
  297.  P.open(W,x,y);        // position (x,y) on W
  298.  
  299.  
  300.  
  301.  
  302. graph editor
  303. -----------
  304.  
  305. A simple graph editor:
  306. (sources in src/window/graph_edit.c)
  307.  
  308. void graph_edit(window& W, GRAPH<point,int>& G, bool dir=true,bool redraw=true);
  309.  
  310.                               G can be edited in winodw W
  311.                               if dir=true G is drawn directed
  312.                               if redraw=true G is redrawn at the beginning
  313.  
  314. header: <LEDA/graph_edit.h>
  315.  
  316. example: prog/graphics/matching.c
  317.  
  318.  
  319.  
  320.  
  321.  
  322. Drawing arcs:
  323. ------------
  324.  
  325. void W.draw_arc(point p,point q,double r,color=black)
  326. void W.draw_arc_arrow(point p,point q,double r,color=black)
  327. void W.draw_arc_edge(point p,point q,double r,color=black)
  328. void W.draw_arc_edge_arrow(point p,point q,double r,color=black)
  329.                          
  330.                                draws a circular arc (edge, arrow)
  331.                                with radius r from p to q with the
  332.                                center lying  to the right of the 
  333.                                directed segment p--->q. p--->q
  334.                                can also be specified by a segment (s)
  335.                                or 4 double coordinates (px,py,qx,qy)
  336.  
  337.  
  338.  
  339. Fonts:
  340. -----
  341.  
  342. LEDA uses three text fonts:
  343.  
  344. text_font:  for normal text (W.draw_text, ...)
  345. bold_font:  for node labels (W.draw_text_node, W.draw_int_node, ...)
  346. mesg_font:  for messages (W.message)
  347.  
  348. You can load different fonts with:
  349.  
  350. bool W.load_text_font(string fn)
  351. bool W.load_bold_font(string fn)
  352. bool W.load_message_font(string fn)
  353.  
  354. All 3 functions return false, if the corresponding font is not available.
  355.  
  356.  
  357.  
  358.  
  359. Additional operations:
  360. ---------------------
  361.  
  362. int  W.read_event(int& but, double& x, double& y)
  363.                                    waits for next event in window W and returns
  364.                                    it. but = mouse button, (x,y) position in W. 
  365.                                    Possible events are defined in 
  366.                                    impl/x_window.h:
  367.                                    button_press_event
  368.                                    button_release_event
  369.                                    motion_event ... 
  370.  
  371. (see prog/graphics/event.c)
  372.  
  373.  
  374.  
  375. void W.flush()                     flush output buffer
  376. void W.set_flush(bool b)           if b = true  flush after each output
  377.                                    
  378. void W.set_frame_label(string s)   set frame label (temporarily) to s
  379. void W.reset_frame_label()         restore standard frame label
  380.  
  381. unsigned W.button_press_time()     return time-stamp of last button click (msec)
  382.  
  383.  
  384.  
  385.  
  386. (non-member) functions:
  387. ----------------------
  388.  
  389. int read_mouse(window*& w, double& x, double& y)
  390.                                    waits for mouse input
  391.                                    w = pointer to the corresonding window,
  392.                                    (x,y) = position in *w
  393.                                    returns pressed button
  394. (see prog/graphics/windows.c)
  395.  
  396.  
  397.                                  
  398. void put_back_event()
  399.                                    puts last event back to the stream of events
  400.  
  401. (see prog/graphics/windows.c)
  402.  
  403.  
  404.